#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <random>
#include <set>
#include <vector>
#include <ctime>
 
static const unsigned seek_count = 1000000;
volatile int nocheat;


#ifndef _MSC_VER
template<typename C>
auto begin(C &&c) -> decltype(std::forward<C>(c).begin()) { return std::forward<C>(c).begin(); }
template<typename C>
auto end(C &&c) -> decltype(std::forward<C>(c).end()) { return std::forward<C>(c).end(); }
#endif

clock_t search_set(int N) {
  nocheat = 0;
  auto r = std::bind(std::uniform_int_distribution<int>(0,N-1),std::default_random_engine());
  std::set<int> s;
  for(int i=0;i<N;++i) {
    s.insert(i);
  }
  clock_t start = clock();
  for(int i=0;i<seek_count;++i) {
    int findme = r();
    auto iter = s.find(findme);
    nocheat += *iter;
  }
  clock_t end = clock();
  return end-start;
}
 
clock_t search_vector(int N) {
  nocheat = 0;
  auto r = std::bind(std::uniform_int_distribution<int>(0,N-1),std::default_random_engine());
  std::vector<int> s;
  for(int i=0;i<N;++i) {
    s.push_back(i);
  }
  clock_t start = clock();
  for(int i=0;i<seek_count;++i) {
    int findme = r();
    auto iter = std::lower_bound(begin(s),end(s),findme);
    if (iter == s.end() || *iter<findme)
      iter = s.end();
    nocheat += *iter;
  }
  clock_t end = clock();
  return end-start;
}
 
int main()
{
  const int N = 100000;
  int time;
 
#if defined(WIN32)
  std::cout.imbue(std::locale("English_United States.1251"));
#endif
 
  std::cout << "Time for N searches where N = " << N << "\n";
  time = search_set(N);
  std::cout << "set returned " << nocheat<< " in " << time << " ticks\n";
  time = search_vector(N);
  std::cout << "vector returned " << nocheat<< " in " << time << " ticks\n";
 
  return 0;
}
